題目連結: Single Number

題目描述為給定一非空的整數陣列，裡面有一個元素只出現一次(single number)，其他都出現兩次。要我們找出 single numer。
題目有補充說明希望我們的時間複雜度為 O(N)，且空間複雜度為 O(1)。

例子 1: [2,2,1], output=1。
例子 2: [4,1,2,1,2], output=4。

思路 1: Hash法

我們可以建立一組 map 來紀錄數字，若該元素出現一次則紀錄下來，當出現第二次時則從 map 刪去。最後檢查 map 中存在的數即可。

• 複雜度評估
  當陣列長度為 N 時，建立 map 需要遍歷整個陣列，檢查數字是否存在也需要遍歷整個 map，此題 map 最終只會有一個元素，時間複雜度為 O(N)。
  此方法另外建立了一組 map ，而map 紀錄元素的過程中，最壞情況為前一半元素均相異，最多需要先紀錄$\left\lceil \frac{N}{2} \right\rceil + 1$ 個元素再開始刪除，空間複雜度為 O(N)。

參考程式碼

func singleNumber(nums []int) int {
    m:=make(map[int]bool)
    
    for _,v:=range nums{
        
        _,exist:=m[v]
        
        if exist{
            delete(m,v)
        }else{
            m[v]=true
        }
    }
    
    for key:=range m{
        if m[key]==true{
            return key
        }
    }
    
    return -1
}

思路 2: Bit Operation

我們可以利用 Day10-Missing Number 提過的解法 3，當對同一數進行兩次 XOR 運算時會抵銷，所以此題只需要對元素中所有數字做 XOR 運算，最終剩下來的數即為所求。

• 複雜度評估
  當陣列長度為 N 時，我們需要遍歷整個陣列進行 XOR 運算，時間複雜度為 O(N)。
  此題只用了常數個變數，空間複雜度為 O(1)。

參考程式碼

func singleNumber(nums []int) int {
   flag:=0
    for _,v:=range nums{
        flag^=v
    }
    return flag
}

小結

解法 1 使用的空間複雜度為 O(N)，未達到題目要求。然而當題目修改為各元素均出現 k 次，或者 single number 不只一個時，解法 1 只需要稍做修改。
解法 2 為昨天所提 bit operation 的應用。

我將解法1、2加上簡單的測試，上傳程式碼到此。